// https://leetcode.cn/problems/n-queens/description/

// 算法思路总结：
// 1. 回溯算法解决N皇后问题
// 2. 按行放置皇后，避免行冲突
// 3. 使用三个标记数组：列、主对角线、副对角线
// 4. 对角线映射：visDig1[i-row+n]（主对角），visDig2[i+row]（副对角）
// 5. 放置n个皇后后保存当前棋盘状态
// 6. 时间复杂度：O(n!)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <cstring>
#include <vector>
#include <algorithm>

class Solution 
{
public:
    vector<vector<string>> ret;
    vector<string> path;
    int _n;
    bool visCol[10], visDig1[20], visDig2[20];

    vector<vector<string>> solveNQueens(int n) 
    {
        _n = n;
        ret.clear();
        path.clear();
        memset(visCol, 0, sizeof(visCol));
        memset(visDig1, 0, sizeof(visDig1));
        memset(visDig2, 0, sizeof(visDig2));

        path.resize(n, string(n, '.'));

        dfs(0);

        return ret;
    }

    void dfs(int row)
    {
        if (row == _n)
        {
            ret.push_back(path);
            return ;
        }

        for (int i = 0 ; i < _n ; i++)
        {
            if (path[row][i] == '.' && visCol[i] == false && visDig1[i - row + _n] == false && visDig2[i + row] == false)
            {
                path[row][i] = 'Q';
                visCol[i] = true;
                visDig1[i - row + _n] = true;
                visDig2[i + row] = true;

                dfs(row + 1);

                path[row][i] = '.';
                visCol[i] = false;
                visDig1[i - row + _n] = false;
                visDig2[i + row] = false;
            }
        }
    }

    void printSolutions(const vector<vector<string>>& solutions, int n) 
    {
        cout << "N = " << n << " 的解决方案，共 " << solutions.size() << " 个解：" << endl;
        cout << "==========================================" << endl;
    
        for (int i = 0; i < solutions.size(); i++) 
        {
            cout << "解决方案 " << i + 1 << ":" << endl;
            for (const auto& row : solutions[i]) 
            {
                for (char c : row) 
                {
                    cout << c << " ";
                }
                cout << endl;
            }
            cout << "-------------------" << endl;
        }
        cout << endl;
    }
};

int main()
{
    int n1 = 4, n2 = 1;
    Solution sol;

    auto vvs1 = sol.solveNQueens(n1);
    auto vvs2 = sol.solveNQueens(n2);

    sol.printSolutions(vvs1, n1); 
    sol.printSolutions(vvs2, n2); 

    return 0;
}